package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.base.TreeNode;
import com.xsherl.leetcode.utils.PrintUtils;

import java.util.HashMap;
import java.util.LinkedList;

public class ConstructBinaryTreeFromPreorderAndInorderTraversal {


    /**
     * 前序遍历是先遍历根节点，然后在依次遍历左子树和右子树， 所以第一个元素就是最顶层的根节点
     * 中序遍历就是先遍历左子树，然后再依次遍历根节点和右子树，所以找到根节点，左边的元素都是左子树，右边的元素都是右子树
     * 因此我们可以按前序遍历来找到根节点， 然后通过递归来构建树,
     * 又因为先找到的节点除根节点外是属于左子树的节点，所以优先构建左子树
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int m = preorder.length;
        LinkedList<Integer> deque = new LinkedList<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int j = 0; j < m; ++j){
            map.put(inorder[j], j);
        }
        for (int val : preorder) {
            deque.add(map.get(val));
        }
        return buildTree(inorder, deque, 0, m - 1);
    }

    public TreeNode buildTree(int[] inorder, LinkedList<Integer> deque, int inorderBegin, int inorderEnd){
        if (deque.isEmpty()){
            return null;
        }
        if (inorderBegin > inorderEnd){
            return null;
        }
        int index = deque.poll();
        int val = inorder[index];
        TreeNode root = new TreeNode(val);
        root.left = buildTree(inorder, deque, inorderBegin, index - 1);
        root.right = buildTree(inorder, deque, index + 1, inorderEnd);
        return root;
    }

//    public TreeNode buildTree(int inorderBegin, int inorderEnd){
//        if (inorderBegin > inorderEnd){
//            return null;
//        }
//        int minIndex = inorderBegin;
//        int min = inorderIndexes[inorderBegin];
//        for (int i = inorderBegin; i <= inorderEnd; ++i){
//            if (min > inorderIndexes[i]){
//                minIndex = i;
//            }
//        }
//        TreeNode root = new TreeNode(inorder[minIndex]);
//        root.left = buildTree( inorderBegin, minIndex - 1);
//        root.right = buildTree(minIndex + 1, inorderEnd);
//        return root;
//    }

    public static void main(String[] args) {
        int[] preorder = {1, 2, 3};
        int[] inorder = {3, 2, 1};
        TreeNode tree = new ConstructBinaryTreeFromPreorderAndInorderTraversal().buildTree(preorder, inorder);
        System.out.println();
        PrintUtils.println(tree);
    }
}
